package com.xqx.shellSort;

public class ShellSort {
    public static void shell_sort(int[] arr, int lenth) {
        int temp = 0;
        int incre = lenth;

        while (true) {
            incre = incre / 2;

            for (int i = 0; i < incre; i++) {  //根据增量分为若干子序列
                for (int j = i + incre; j < lenth; j += incre) {
                    for (int k = j; k > i; k -= incre) {
                        if (arr[k] < arr[k - incre]) {
                            temp = arr[k - incre];
                            arr[k - incre] = arr[k];
                            arr[k] = temp;
                        } else {
                            break;
                        }
                    }
                }
            }

            if (incre == 1) {
                break;
            }
        }
    }
}
/*
基本思想：
        在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
        然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。*/

//三层循环